package likou;

import java.util.*;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/28 05:26
 */
public class _493 {
    public static void main(String[] args) {
        System.out.println(reversePairs2(new int[]{1, 3, 2, 3, 1}));
    }

    public static int reversePairs(int[] nums) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            List<Integer> list = !map.containsKey(nums[i]) ? new ArrayList<>() : map.get(nums[i]);
            list.add(i);
            map.put(nums[i], list);
        }
        List<Integer> list = new ArrayList<>(map.keySet());
        list.sort((o1, o2) -> {
            if (o1 >= 0 && o2 >= 0) {
                return o2 - o1;
            } else {
                return o1 - o2;
            }
        });
        int daan = 0;
        for (int i = 0; i < list.size(); i++) {
            int left = list.get(i);
            List<Integer> list1 = map.get(left);
            for (int j = list.size() - 1; j > i; j--) {
                int right = list.get(j);
                if (left - right > right || right < 0) {
                    List<Integer> list2 = map.get(list.get(j));
                    for (int now : list1) {
                        for (int now2 : list2) {
                            if (now < now2) {
                                daan++;
                            }
                        }
                    }
                } else {
                    break;
                }
            }
            if (list.get(i) < 0) {
                daan = daan + list1.size() * (list1.size() - 1) / 2;
            }
        }
        return daan;
    }


    /**
     * 归并排序，直接分开，然后从前往后比较
     *
     * @param nums
     * @return
     */
    public static int reversePairs2(int[] nums) {
        int[] buffer = new int[nums.length / 2 + 1];
        return reversePairs(nums, buffer, 0, nums.length - 1);
    }

    /**
     * @param nums   数组 排序好后的位置
     * @param buffer 辅助存储。记录当前分支的前半部分，排序时，与后半部分
     * @param left   左边下标
     * @param right  右边下标
     * @return
     */
    private static int reversePairs(int[] nums, int[] buffer, int left, int right) {
        if (right <= left) {
            return 0;
        }

        int count = 0;
        int mid = (left + right) / 2;
        int leftPlus = reversePairs(nums, buffer, left, mid);
        int rightPlus = reversePairs(nums, buffer, mid + 1, right);
        count += leftPlus + rightPlus;

        int i = left;
        int j = mid + 1;
        int add = 0;

        //数组的前一半和后一半已经把结果存入count了。
        //所以只需要把前一半拿来和后一半比较就行了。
        while (i <= mid) {
            while (j <= right && nums[i] > nums[j] * 2L) {
                j++;
            }
            //j-mid是j移动的距离。-1是当前右边的下标
            add += j - mid - 1;
            i++;
        }
        count += add;


        /**
         * nums：原数组
         * left：从原数组的某个下标位置开始
         * buffer：目标数组
         * 0：目标数组的起始位置
         * mid-left+1：要copy的长度
         */
        System.arraycopy(nums, left, buffer, 0, mid - left + 1);
        i = 0;
        int bright = mid - left;//buffer里面的最大下标
        j = mid + 1;
        int k = left;
        //排序有利于上面的while操作，即所有较小的，放在前面，较大的放在后面，便于while的结束。
        //一个归并分支的前面部分和后面部分排序
        while (i <= bright && j <= right) {
            //只能保证前面部分对于后面的部分是有序的，每次这样之后，后面的部分全是有序，前面部分也全部有序
            if (buffer[i] < nums[j]) {
                nums[k++] = buffer[i++];
            } else {
                nums[k++] = nums[j++];
            }
        }
        while (i <= bright) {
            nums[k] = buffer[i];
            k++;
            i++;
        }
        return count;
    }
}
